import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description: 排序的模板(算法书)
 * User:岁亮亮
 * Date:2024-06-21
 * TIME:21:32
 */
public class Example {

    /**
     * 直接插入排序
     * 对第一种 最坏需要 N*2/2次比较和交换 最好需要 N-1 次比较和 0 次交换
     * 时间复杂度 O(N*2)
     * 空间复杂度 O(1)
     * 稳定性 稳定
     * 适应于 数组越有序 排序速度就越快 时间效率就越高
     * @param str
     */
    //直接两两比较进行交换
    public static void insertSort(Comparable[] str){
        for (int i = 1; i < str.length; i++) {
           for(int j = i; j >0 && compare(str[j],str[j-1]);j--){
               each(str,j,j-1);
           }
        }
    }
    //将索引大的主键往后移动一位到合适位置进行插入
    public static void insertSort2(Comparable[] str){
        for (int i = 1; i < str.length; i++) {
            Comparable tmp = str[i];
            int j = i-1;
            for(; j >=0 && compare(tmp,str[j]);j--){
                str[j+1] = str[j];
            }
            str[j+1] = tmp;
        }
    }

    /**
     * 希尔排序 对数组进行分组 分成 k 个子数组 对其进行排序 使其数组为 k ge有序子数组
     *
     * @param str
     */
   public static void shell(Comparable[] str){
        int N = str.length;
        int k = 1;
        while ((N/3) > k){
            k = k*3 + 1;
        }
        while (k>=1) {
            for (int i = k; i < str.length; i++) {
                for (int j = i; j > k && compare(str[j], str[j - k]); j -= k) {
                    each(str, j, j - k);
                }
            }
            k = k/3;
        }
   }
   public static void shell2(Comparable[] str){
       int N = str.length;
       int k = N/2;
      while (k >= 1){
          N = N / 2;
          forShell(str,k);
          k = N / 2;
      }
   }

    private static void forShell(Comparable[] str, int k) {
        for (int i = k; i <str.length ; i++) {
            Comparable tmp = str[i];
            int j = i-k;
            for(; j >=0 && compare(tmp,str[j]);j-=k){
                str[j+k] = str[j];
            }
            str[j+k] = tmp;
        }
    }


    /**
     * 选择排序
     * @param str
     */
    public static void selectSort(Comparable[] str){
        for (int i = 0; i < str.length; i++) {
            int minIndex = i;
            for(int j = i + 1; j < str.length; j++){
               if(compare(str[j],str[minIndex])){
                   minIndex = j;
               }
            }
            each(str,i,minIndex);
        }
    }
    public static void selectSort2(Comparable[] str) {
        for (int i = 0; i < str.length; i++) {
            Comparable tmp = str[i];
            for (int j = i + 1; j < str.length; j++) {
                if(compare(str[j],tmp)){
                   each(str,i,j);
                   tmp = str[j];
                }
            }
        }
    }
    //双向选择排序
    public static void selectSort3(Comparable[] str){
        int left = 0;
        int right = str.length-1;
        while (left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left; i < right ; i++) {
                if(compare(str[i+1],str[minIndex])){
                    minIndex = i+1;
                }
                if(compare(str[maxIndex],str[i+1])){
                    maxIndex = i+1;
                }
            }
            each(str,left,minIndex );
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            each(str,right,maxIndex);
            left++;
            right--;
        }

    }

    /**
     * 堆排序
     * @param str
     */
   public static void heapSort(Comparable[] str){
        int len = str.length;
        for(int parent = (len-1-1)/2; parent >= 0;parent--){
            siftDown(str,parent,len);
        }
        while (len > 1){
            each(str,0,len-1);
            siftDown(str,0,len-1);
            len--;
        }
   }

    private static void siftDown(Comparable[] str, int parent, int len) {
       int child = parent*2 +1;
       while (child < len){
           if(child + 1<len && compare(str[child],str[child+1])){
               child = child+1;
           }
           if(compare(str[parent],str[child])){
               each(str,parent,child);
           }
           parent = child;
           child = parent*2 + 1;
       }
    }

    /**
     * 交换排序中的 冒泡排序
     * @param str
     */
    public static void bubbleSort(Comparable[] str){

        for (int i = 0; i < str.length-1; i++) {
            boolean flag = false;
            for(int j = 1; j < str.length;j++){
                if(compare(str[j],str[j-1])){
                    each(str,j,j-1);
                    flag = true;
                }
            }
            if(!flag){
                return;
            }
        }

    }


        public static void bubbleSort2(Comparable[] str){
        for (int i = 0; i < str.length-1; i++) {
            boolean flag = false;
            for(int j = 0;j < str.length-1;j ++){
                if(compare(str[j+1],str[j])){
                    each(str,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                return;
            }
        }
    }
    public static void bubbleSort3(Comparable[] str){
        for (int i = 0; i < str.length-1; i++) {
            for (int j = 0; j < str.length-1-i; j++) {
                if(compare(str[j+1],str[j])){
                    each(str,j,j+1);
                }

            }

        }
    }

    /**
     * 快速排序
     * 时间复杂的 最好情况下O(N*logN)  最坏情况 O(N*N)(倒叙或者有序情况 递归的层数最大为N;)
     * 空间复杂度 树的高度即递归的层数 logN;
     * @param str
     */

    public static void quickSort(Comparable[]str){
        forQuickSort(str,0,str.length-1);
    }

    private static void forQuickSort(Comparable[] str, int start, int end) {
        if(start>=end){
            return;
        }
        //优化 在递归到最后几层的时候 数组已经基本基于有序并且最后几层存在大多数的元素
        //     不用再耗费栈帧进行递归下去 直接用插入排序来完成最后的排序
        if((end - start) < 20){
            insertQUickSort(str,start,end);
            return;
        }
        int muddle = muddleNum(str,start,end);
        each(str,start,muddle);
        int benchmark = quickHonare(str,start,end);
        forQuickSort(str,start,benchmark-1);
        forQuickSort(str,benchmark+1,end);
    }
    public static void quickSortNor(Comparable[] str){
        int start = 0;
        int end = str.length-1;
        Stack<Integer> stack = new Stack<>();
        int benchmark = quickHonare(str,start,end);
       if(benchmark-1>start){
           stack.push(start);
           stack.push(benchmark-1);
       }
       if(benchmark+1<end){
           stack.push((benchmark+1));
           stack.push(end);
       }
       while (!stack.isEmpty()){
           end = stack.pop();
           start = stack.pop();
           benchmark = quickHonare(str,start,end);
           if(benchmark-1>start){
               stack.push(start);
               stack.push(benchmark-1);
           }
           if(benchmark+1<end){
               stack.push((benchmark+1));
               stack.push(end);
           }
       }
    }
    //优化 快排的插入排序
    private static void insertQUickSort(Comparable[] str, int start, int end) {
            for (int i = start + 1; i <= end; i++) {
                Comparable tmp = str[i];
                int j = i-1;
                for(; j >=start&& compare(tmp,str[j]);j--){
                    str[j+1] = str[j];
                }
                str[j+1] = tmp;

        }
    }

    //优化 取基准值时 三位取中法
    private static int muddleNum(Comparable[] str, int start, int end) {
        int middle = (end + start)/2;
       if(compare(str[start],str[end])){
           if(compare(str[middle],str[start])){
               return start;
           }
           if(compare(str[end],str[middle])){
               return end;
           }
           return middle;
       }
       else if(compare(str[end],str[start])){
           if(compare(str[start],str[end])){
               return end;
           }
           if(compare(str[start],str[middle])){
               return start;
           }
           return middle;
       }
      return middle;
    }

    //honare法 求基准值并排序
    private static int quickHonare(Comparable[] str, int left, int right) {
        Comparable tmp = str[left];
        int index = left;
        while (left < right){
            while(left < right && compare2(tmp,str[right])){
                right--;
            }
            while (left < right && compare2(str[left],tmp)){
                left++;
            }
            each(str,left,right);
        }
        each(str,left,index);
        return left;
    }
    //挖坑法 求基准值
    private static int quickDigHole(Comparable[] str,int left,int right){
        Comparable tmp = str[left];
        int index = left;
        while(left < right){
            while(left < right && compare2(tmp,str[right])){
                right--;
            }
            str[left] = str[right];
            while (left < right && compare2(str[left],tmp)){
                left++;
            }
            str[right] = str[left];
        }
        str[left] = tmp;
        return left;

    }
    //前后指针法求基准值
    private static int quickPointer(Comparable[] str,int left,int right){
        Comparable tmp = str[left];
        int cur = left;
        int prev = left;
        while (cur <= right){
            if(compare(str[cur],tmp) && str[++prev]!=str[cur]){
                each(str,prev,cur);
            }
            cur++;
        }
        each(str,left,prev);
        return prev;
    }

    /**
     * 归并排序 先分解再合并
     * @param str
     */

    public static void mergeSort(Comparable[] str){
        forMergeSort(str,0,str.length-1);
    }

    private static void forMergeSort(Comparable[] str, int start, int end) {
        if(start>=end){
            return;
        }
        int mid = (start + end)/2;
        //分解
        forMergeSort(str,start,mid);
        forMergeSort(str,mid+1,end);
        //合并
        combineMergeSort(str,start,mid,end);
    }
    public static void mergeSortNor(Comparable[] str){
        int gap = 1;
        int left = 0;
        int right = str.length;
        while (gap <= str.length){
            for (int i = 0; i < str.length; i+=gap*2) {
                left = i;
                int mid = left + gap -1;
                right = mid+ gap;
                if(mid >=str.length-1){
                    mid = str.length-1;
                    /*right = str.length-1;*/
                }
                if(right >=str.length-1){
                    right = str.length-1;
                }
                combineMergeSort(str,left,mid,right);
            }
            gap *= 2;
        }
    }

    private static void combineMergeSort(Comparable[] str, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        Comparable[] array = new Comparable[right-left+1];
        int i = 0;//表示array数组的下标
        while(s1 <= e1 && s2 <= e2){
            if(compare2(str[s2],str[s1])){
                array[i++] = str[s2++];
            }
            else {
                array[i++] = str[s1++];
            }
        }
        while (s1 <= e1){
            array[i++] = str[s1++];
        }
        while (s2 <= e2){
            array[i++] = str[s2++];
        }
        for (int j = 0; j < array.length; j++) {
            str[left+j] = array[j];
        }
    }


    //交换
    public static void each(Comparable[] comparables,int i,int j){
        Comparable tmp = comparables[i];
        comparables[i] = comparables[j];
        comparables[j] = tmp;
    }
    //比较
    public static boolean compare(Comparable i,Comparable j){
        return i.compareTo(j) < 0;
    }
    //快排
    public static boolean compare2(Comparable i,Comparable j){
        return i.compareTo(j) <= 0;
    }

    public static void show(Comparable[] comparables){
        for (int i = 0; i < comparables.length; i++) {
            System.out.print(comparables[i] + " ");
        }
        System.out.println();
    }
    //确认排序后的数组是有序的
    public boolean isSort(Comparable[] comparables){
        for (int i = 0; i < comparables.length; i++) {
            if(!compare(comparables[i],comparables[i+1])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Integer[] integers = new Integer[]{23,34,12,11,56,43,21};
      /* insertSort(integers);
       show(integers);*/
        System.out.println("============");
        /*insertSort2(integers);
        show(integers);*/
       /* shell2(integers);
        show(integers);*/
       /* selectSort3(integers);
        show(integers);*/
        /*heapSort(integers);
        show(integers);*/
       /* bubbleSort(integers);
        show(integers);*/
       /* quickSort(integers);
        show(integers);*/
       /* quickSortNor(integers);
        show(integers);*/
        mergeSortNor(integers);
        show(integers);

    }
}
